{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Pairs Satisfying Inequality"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #满足不等式的数对数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums1</code> 和&nbsp;<code>nums2</code>&nbsp;，两个数组的大小都为&nbsp;<code>n</code>&nbsp;，同时给你一个整数&nbsp;<code>diff</code>&nbsp;，统计满足以下条件的&nbsp;<strong>数对&nbsp;</strong><code>(i, j)</code>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; j &lt;= n - 1</code>&nbsp;<b>且</b></li>\n",
    "\t<li><code>nums1[i] - nums1[j] &lt;= nums2[i] - nums2[j] + diff</code>.</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回满足条件的 <strong>数对数目</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [3,2,5], nums2 = [2,2,1], diff = 1\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "总共有 3 个满足条件的数对：\n",
    "1. i = 0, j = 1：3 - 2 &lt;= 2 - 2 + 1 。因为 i &lt; j 且 1 &lt;= 1 ，这个数对满足条件。\n",
    "2. i = 0, j = 2：3 - 5 &lt;= 2 - 1 + 1 。因为 i &lt; j 且 -2 &lt;= 2 ，这个数对满足条件。\n",
    "3. i = 1, j = 2：2 - 5 &lt;= 2 - 1 + 1 。因为 i &lt; j 且 -3 &lt;= 2 ，这个数对满足条件。\n",
    "所以，我们返回 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums1 = [3,-1], nums2 = [-2,2], diff = -1\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "没有满足条件的任何数对，所以我们返回 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums1.length == nums2.length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= nums1[i], nums2[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= diff &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-pairs-satisfying-inequality](https://leetcode.cn/problems/number-of-pairs-satisfying-inequality/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-pairs-satisfying-inequality](https://leetcode.cn/problems/number-of-pairs-satisfying-inequality/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,5]\\n[2,2,1]\\n1', '[3,-1]\\n[-2,2]\\n-1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        def merge_sort(arr:List[int])->int:\n",
    "            if len(arr)==1:return 0\n",
    "            mid=(len(arr))//2\n",
    "            a=arr[:mid]\n",
    "            b=arr[mid:]\n",
    "            cnt=merge_sort(a)+merge_sort(b)\n",
    "            i,n=0,len(a)\n",
    "            for x in b:\n",
    "                while i<n and a[i]<=x+diff:\n",
    "                    i+=1\n",
    "                cnt+=i\n",
    "            cur=i=j=0\n",
    "            m=len(b)\n",
    "            while True:\n",
    "                if i==n:\n",
    "                    arr[cur:]=b[j:]\n",
    "                    break\n",
    "                if j==m:\n",
    "                    arr[cur:]=a[i:]\n",
    "                    break\n",
    "                if a[i]<b[j]:\n",
    "                    arr[cur]=a[i]\n",
    "                    i+=1\n",
    "                else:\n",
    "                    arr[cur]=b[j]\n",
    "                    j+=1\n",
    "                cur+=1\n",
    "            return cnt\n",
    "        \n",
    "        a=[x-y for x,y in zip(nums1,nums2)]\n",
    "        return merge_sort(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "# nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "\n",
    "class Solution:\n",
    "  def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "    n = len(nums1)\n",
    "    b = [nums1[i] - nums2[i] for i in range(n)]\n",
    "    mn = min(b)\n",
    "    mx = max(b)\n",
    "    offset = 1 - mn\n",
    "    bit = BIT(mx - mn + 1)\n",
    "    ans = 0\n",
    "    for i in range(n):\n",
    "      cur = nums1[i] - nums2[i] + diff\n",
    "      if cur >= mn and cur <= mx:\n",
    "        j = cur + offset\n",
    "        ans += bit.query(j)\n",
    "      elif cur > mx:\n",
    "        ans += bit.query(mx - mn + 1)\n",
    "      bit.update(nums1[i] - nums2[i] + offset)\n",
    "    return ans\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: list[int], nums2: list[int], diff: int) -> int:\n",
    "        def merge_sort(arr :List[int]) -> int:\n",
    "            if len(arr)<=1:\n",
    "                return 0\n",
    "            mid=len(arr)//2\n",
    "            a=arr[:mid]\n",
    "            b=arr[mid:]\n",
    "            cnt=merge_sort(a)+merge_sort(b)\n",
    "            i,n=0,len(a)\n",
    "            for x in b:\n",
    "                while i<n and a[i]<=x+diff:\n",
    "                    i+=1\n",
    "                cnt+=i\n",
    "            cur=i=j=0  ##指针\n",
    "            m=len(b)\n",
    "            while True:\n",
    "                if i==n:\n",
    "                    arr[cur:]=b[j:]\n",
    "                    break\n",
    "                if j==m:\n",
    "                    arr[cur:]=a[i:]\n",
    "                    break\n",
    "                if a[i]<b[j]:\n",
    "                    arr[cur]=a[i]\n",
    "                    cur+=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    arr[cur]=b[j]\n",
    "                    cur+=1\n",
    "                    j+=1\n",
    "            \n",
    "            return cnt\n",
    "        difference=[x-y for x,y in zip(nums1,nums2)]\n",
    "        return merge_sort(difference)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bisect_right(self, nums, target):\n",
    "        l, r = 0, len(nums)\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if nums[m] <= target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        return l\n",
    "    \n",
    "    def bisect_left(self, nums, target):\n",
    "        l, r = 0, len(nums)\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if nums[m] < target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        return l\n",
    "    \n",
    "    def bisect(self, nums, target):\n",
    "        l, r = 0, len(nums)\n",
    "        while l < r:\n",
    "            m = (l + r) >> 1\n",
    "            if nums[m] == target:\n",
    "                return m\n",
    "            elif nums[m] < target:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m\n",
    "        return -1\n",
    "    \n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        a = [x-y for x, y in zip(nums1, nums2)]\n",
    "        b = sorted(a) # 将a的值域离散化，因为树状数组的索引表示的是值域\n",
    "        bit = BIT(len(a)+1)\n",
    "        ans = 0\n",
    "        for x in a:\n",
    "            j = self.bisect_right(b, x+diff) # 离散化后的下标,bisect_right是>的第一个\n",
    "            ans += bit.query(j) # 在树状数组中查找<=x+diff的总数（前缀区间查询）,j不应+1，假设j=0，说明没有，bit.query(0)会返回0\n",
    "            # 因为二分一定能二分到，用self.bisect, self.bisect_left都可以，但是bisect_right不行，因为bisect_right得到的是>的第一个，没有等号\n",
    "            bit.add(self.bisect(b, x)+1, 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, i, val):\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += val\n",
    "            i += self.low_bit(i)\n",
    "\n",
    "    def query(self, i):\n",
    "        ans = 0\n",
    "        while i > 0:\n",
    "            ans += self.tree[i]\n",
    "            i -= self.low_bit(i)\n",
    "        return ans\n",
    "    \n",
    "    def low_bit(self, x):\n",
    "        return x & -x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: list[int], nums2: list[int], diff: int) -> int:\n",
    "        def merge_sort(arr :List[int]) -> int:\n",
    "            if len(arr)<=1:\n",
    "                return 0\n",
    "            mid=len(arr)//2\n",
    "            a=arr[:mid]\n",
    "            b=arr[mid:]\n",
    "            cnt=merge_sort(a)+merge_sort(b)\n",
    "            i,n=0,len(a)\n",
    "            for x in b:\n",
    "                while i<n and a[i]<=x+diff:\n",
    "                    i+=1\n",
    "                cnt+=i\n",
    "            cur=i=j=0  ##指针\n",
    "            m=len(b)\n",
    "            while True:\n",
    "                if i==n:\n",
    "                    arr[cur:]=b[j:]\n",
    "                    break\n",
    "                if j==m:\n",
    "                    arr[cur:]=a[i:]\n",
    "                    break\n",
    "                if a[i]<b[j]:\n",
    "                    arr[cur]=a[i]\n",
    "                    cur+=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    arr[cur]=b[j]\n",
    "                    cur+=1\n",
    "                    j+=1\n",
    "            \n",
    "            return cnt\n",
    "        difference=[x-y for x,y in zip(nums1,nums2)]\n",
    "        return merge_sort(difference)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 离散化的BIT\n",
    "from bisect import *\n",
    "class DiscreteBIT:\n",
    "    def __init__(self, nums):\n",
    "        self.nums = nums.copy() \n",
    "        self.nums.sort()\n",
    "        # 用nums数组离散化可以做二分(求不在里面的数)，比起用map，只是把logn变成了2logn\n",
    "        self.n = len(self.nums)\n",
    "        self.tree = [0] * (self.n + 1)\n",
    "        # for x in nums:\n",
    "        #     self.update(x, 1) # TODO: 根据需要调整，这儿记录的是区间元素个数\n",
    "\n",
    "\n",
    "    def get_idx(self, val):\n",
    "        # bisect_right本身已经是开区间, 所以相当于最右边元素 + 1\n",
    "        return bisect_right(self.nums, val)\n",
    "    \n",
    "    # 单点修改 \n",
    "    def update(self, i, x):\n",
    "        i = self.get_idx(i)\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += x\n",
    "            i += i & -i\n",
    "\n",
    "    # 区间查询, [1, i]区间和\n",
    "    def query(self, i):\n",
    "        i = self.get_idx(i)\n",
    "        res = 0\n",
    "        while i:\n",
    "            res += self.tree[i]\n",
    "            i -= i & -i\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        tmp = [a - b for a, b in zip(nums1, nums2)]\n",
    "        bit = DiscreteBIT(tmp)\n",
    "        ans = 0\n",
    "        for num in tmp:\n",
    "            ans += bit.query(num + diff)\n",
    "            bit.update(num, 1)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "# nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "\n",
    "class Solution:\n",
    "  def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "    n = len(nums1)\n",
    "    b = [nums1[i] - nums2[i] for i in range(n)]\n",
    "    mn = min(b)\n",
    "    mx = max(b)\n",
    "    offset = 1 - mn\n",
    "    bit = BIT(mx - mn + 1)\n",
    "    ans = 0\n",
    "    for i in range(n):\n",
    "      cur = nums1[i] - nums2[i] + diff\n",
    "      if cur >= mn and cur <= mx:\n",
    "        j = cur + offset\n",
    "        ans += bit.query(j)\n",
    "      elif cur > mx:\n",
    "        ans += bit.query(mx - mn + 1)\n",
    "      bit.update(nums1[i] - nums2[i] + offset)\n",
    "      print(i, ans)\n",
    "    return ans\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# from typing import List\n",
    "# from bisect import bisect_left\n",
    "# # nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "\n",
    "# class Solution:\n",
    "#   def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "#     n = len(nums1)\n",
    "#     b = sorted([nums1[i] - nums2[i] for i in range(n)])\n",
    "#     bit = BIT(n)\n",
    "#     ans = 0\n",
    "#     for i in range(n):\n",
    "#       cur = nums1[i] - nums2[i] + diff\n",
    "#       if cur > b[-1]:\n",
    "#         ans += bit.query(n)\n",
    "#       elif cur < b[0]:\n",
    "#         pass\n",
    "#       else:\n",
    "#         j = bisect_left(b, cur) + 1\n",
    "#         ans += bit.query(j - (0 if cur in b else 1))\n",
    "#       k = bisect_left(b, nums1[i] - nums2[i]) + 1\n",
    "#       bit.update(k)\n",
    "#     return ans\n",
    "\n",
    "# class BIT:\n",
    "#   def __init__(self, n) -> None:\n",
    "#     # 数组下标1开始为有效值\n",
    "#     self.tree = [0] * (n + 1)\n",
    "#   def update(self, i):\n",
    "#     while i < len(self.tree):\n",
    "#       self.tree[i] += 1\n",
    "#       i += i & -i\n",
    "#   def query(self, i):\n",
    "#     ans = 0\n",
    "#     while i > 0:\n",
    "#       ans += 1\n",
    "#       i -= i & -i\n",
    "#     return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left\n",
    "# nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "\n",
    "class Solution:\n",
    "  def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "    n = len(nums1)\n",
    "    b = [nums1[i] - nums2[i] for i in range(n)]\n",
    "    mn = min(b)\n",
    "    mx = max(b)\n",
    "    offset = 1 - mn\n",
    "    bit = BIT(mx - mn + 1)\n",
    "    ans = 0\n",
    "    for i in range(n):\n",
    "      cur = nums1[i] - nums2[i] + diff\n",
    "      if cur >= mn and cur <= mx:\n",
    "        j = cur + offset\n",
    "        ans += bit.query(j)\n",
    "      elif cur > mx:\n",
    "        ans += bit.query(mx - mn + 1)\n",
    "      bit.update(nums1[i] - nums2[i] + offset)\n",
    "    return ans\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# from typing import List\n",
    "# from bisect import bisect_left\n",
    "# # nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "\n",
    "# class Solution:\n",
    "#   def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "#     n = len(nums1)\n",
    "#     b = sorted([nums1[i] - nums2[i] for i in range(n)])\n",
    "#     bit = BIT(n)\n",
    "#     ans = 0\n",
    "#     for i in range(n):\n",
    "#       cur = nums1[i] - nums2[i] + diff\n",
    "#       if cur > b[-1]:\n",
    "#         ans += bit.query(n)\n",
    "#       elif cur < b[0]:\n",
    "#         pass\n",
    "#       else:\n",
    "#         j = bisect_left(b, cur) + 1\n",
    "#         ans += bit.query(j - (0 if cur in b else 1))\n",
    "#       k = bisect_left(b, nums1[i] - nums2[i]) + 1\n",
    "#       bit.update(k)\n",
    "#     return ans\n",
    "\n",
    "# class BIT:\n",
    "#   def __init__(self, n) -> None:\n",
    "#     # 数组下标1开始为有效值\n",
    "#     self.tree = [0] * (n + 1)\n",
    "#   def update(self, i):\n",
    "#     while i < len(self.tree):\n",
    "#       self.tree[i] += 1\n",
    "#       i += i & -i\n",
    "#   def query(self, i):\n",
    "#     ans = 0\n",
    "#     while i > 0:\n",
    "#       ans += 1\n",
    "#       i -= i & -i\n",
    "#     return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: list[int], nums2: list[int], diff: int) -> int:\n",
    "        def merge_sort(arr :List[int]) -> int:\n",
    "            if len(arr)<=1:\n",
    "                return 0\n",
    "            mid=len(arr)//2\n",
    "            a=arr[:mid]\n",
    "            b=arr[mid:]\n",
    "            cnt=merge_sort(a)+merge_sort(b)\n",
    "            i,n=0,len(a)\n",
    "            for x in b:\n",
    "                while i<n and a[i]<=x+diff:\n",
    "                    i+=1\n",
    "                cnt+=i\n",
    "            cur=i=j=0  ##指针\n",
    "            m=len(b)\n",
    "            while True:\n",
    "                if i==n:\n",
    "                    arr[cur:]=b[j:]\n",
    "                    break\n",
    "                if j==m:\n",
    "                    arr[cur:]=a[i:]\n",
    "                    break\n",
    "                if a[i]<b[j]:\n",
    "                    arr[cur]=a[i]\n",
    "                    cur+=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    arr[cur]=b[j]\n",
    "                    cur+=1\n",
    "                    j+=1\n",
    "            return cnt\n",
    "        difference=[x-y for x,y in zip(nums1,nums2)]\n",
    "        return merge_sort(difference)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: list[int], nums2: list[int], diff: int) -> int:\n",
    "        def merge_sort(arr :List[int]) -> int:\n",
    "            if len(arr)<=1:\n",
    "                return 0\n",
    "            mid=len(arr)//2\n",
    "            a=arr[:mid]\n",
    "            b=arr[mid:]\n",
    "            cnt=merge_sort(a)+merge_sort(b)\n",
    "            i,n=0,len(a)\n",
    "            for x in b:\n",
    "                while i<n and a[i]<=x+diff:\n",
    "                    i+=1\n",
    "                cnt+=i\n",
    "            cur=i=j=0  ##指针\n",
    "            m=len(b)\n",
    "            while True:\n",
    "                if i==n:\n",
    "                    arr[cur:]=b[j:]\n",
    "                    break\n",
    "                if j==m:\n",
    "                    arr[cur:]=a[i:]\n",
    "                    break\n",
    "                if a[i]<b[j]:\n",
    "                    arr[cur]=a[i]\n",
    "                    cur+=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    arr[cur]=b[j]\n",
    "                    cur+=1\n",
    "                    j+=1\n",
    "            return cnt\n",
    "        difference=[x-y for x,y in zip(nums1,nums2)]\n",
    "        return merge_sort(difference)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: list[int], nums2: list[int], diff: int) -> int:\n",
    "        def merge_sort(arr :List[int]) -> int:\n",
    "            if len(arr)<=1:\n",
    "                return 0\n",
    "            mid=len(arr)//2\n",
    "            a=arr[:mid]\n",
    "            b=arr[mid:]\n",
    "            cnt=merge_sort(a)+merge_sort(b)\n",
    "            i,n=0,len(a)\n",
    "            for x in b:\n",
    "                while i<n and a[i]<=x+diff:\n",
    "                    i+=1\n",
    "                cnt+=i\n",
    "            cur=i=j=0  ##指针\n",
    "            m=len(b)\n",
    "            while True:\n",
    "                if i==n:\n",
    "                    arr[cur:]=b[j:]\n",
    "                    break\n",
    "                if j==m:\n",
    "                    arr[cur:]=a[i:]\n",
    "                    break\n",
    "                if a[i]<b[j]:\n",
    "                    arr[cur]=a[i]\n",
    "                    cur+=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    arr[cur]=b[j]\n",
    "                    cur+=1\n",
    "                    j+=1\n",
    "            return cnt\n",
    "        difference=[x-y for x,y in zip(nums1,nums2)]\n",
    "        return merge_sort(difference)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Bit:\n",
    "#     def __init__(self,n):\n",
    "#         self.arr = [0]*n\n",
    "#     def add(self,index,v=1):\n",
    "#         while index<len(self.arr):\n",
    "#             self.arr[index]+=v\n",
    "#             index += index&(-index)\n",
    "#     def query(self,index):\n",
    "#         ans = 0\n",
    "#         while index>0:\n",
    "#             ans+=self.arr[index]\n",
    "#             index &= index-1\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "#         arr = [x-y for x,y in zip(nums1,nums2)]\n",
    "#         arr1 = sorted(arr)\n",
    "\n",
    "#         res = 0\n",
    "#         n = len(nums1)\n",
    "#         tree = Bit(n+1)\n",
    "#         ans = 0\n",
    "#         for v in arr:\n",
    "#             i = bisect_right(arr1,v+diff)\n",
    "#             ans+=tree.query(i)\n",
    "#             tree.add(bisect_left(arr1,v)+1)\n",
    "#         return ans\n",
    "\n",
    "\n",
    "        # o(n**2)过不了 不能暴力\n",
    "        record = [0]*len(nums1)\n",
    "        for i in range(len(nums1)):\n",
    "            record[i] = nums1[i]- nums2[i]\n",
    "        def merge_sort(arr):\n",
    "            if len(arr) <= 1:\n",
    "                return 0\n",
    "            mid = len(arr)//2\n",
    "            # count = 0\n",
    "            a = arr[:mid]\n",
    "            b = arr[mid:]\n",
    "            count = merge_sort(a) + merge_sort(b)\n",
    "            index = 0\n",
    "            for i in b:\n",
    "                while index < len(a) and i - a[index]+diff>=0:\n",
    "                    index+=1\n",
    "                count+=index\n",
    "            # for data in b:\n",
    "                # while index<len(a) and data- \n",
    "            i = j = cur = 0\n",
    "            while True:\n",
    "                if i == len(a):\n",
    "                    arr[cur:] = b[j:]\n",
    "                    break\n",
    "                elif j == len(b):\n",
    "                    arr[cur:] = a[i:]\n",
    "                    break\n",
    "                else:\n",
    "                    if a[i]>b[j]:\n",
    "                        arr[cur] = b[j]\n",
    "                        cur+=1\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        arr[cur] = a[i]\n",
    "                        cur+=1\n",
    "                        i+=1\n",
    "            return count\n",
    "        return merge_sort(record)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: list[int], nums2: list[int], diff: int) -> int:\n",
    "        def merge_sort(arr :List[int]) -> int:\n",
    "            if len(arr)<=1:\n",
    "                return 0\n",
    "            mid=len(arr)//2\n",
    "            a=arr[:mid]\n",
    "            b=arr[mid:]\n",
    "            cnt=merge_sort(a)+merge_sort(b)\n",
    "            i,n=0,len(a)\n",
    "            for x in b:\n",
    "                while i<n and a[i]<=x+diff:\n",
    "                    i+=1\n",
    "                cnt+=i\n",
    "            cur=i=j=0  ##指针\n",
    "            m=len(b)\n",
    "            while True:\n",
    "                if i==n:\n",
    "                    arr[cur:]=b[j:]\n",
    "                    break\n",
    "                if j==m:\n",
    "                    arr[cur:]=a[i:]\n",
    "                    break\n",
    "                if a[i]<b[j]:\n",
    "                    arr[cur]=a[i]\n",
    "                    cur+=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    arr[cur]=b[j]\n",
    "                    cur+=1\n",
    "                    j+=1\n",
    "            return cnt\n",
    "        difference=[x-y for x,y in zip(nums1,nums2)]\n",
    "        return merge_sort(difference)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#动态维护arr的前缀和\n",
    "#树状数组从1开始\n",
    "class BIT:\n",
    "\tdef __init__(self,n:int):\n",
    "\t\tself.tree=[0]*n\n",
    "\n",
    "\t#O(logn)\n",
    "\t#arr[i]+=val\n",
    "\tdef add(self,i:int,val:int):\n",
    "\t\twhile i<len(self.tree):\n",
    "\t\t\tself.tree[i]+=val\n",
    "\t\t\ti+=i&-i\n",
    "\n",
    "\t#O(logn)\n",
    "\t#return sum(arr[:i+1])\n",
    "\tdef query(self,i:int)->int:\n",
    "\t\tres=0\n",
    "\t\twhile i>0:\n",
    "\t\t\tres+=self.tree[i]\n",
    "\t\t\ti-=i&-i\n",
    "\t\treturn res\n",
    "\n",
    "\n",
    "#O(nlogn)\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        a=[x-y for x,y in zip(nums1,nums2)]\n",
    "        b=a.copy()\n",
    "        b.sort()\n",
    "        t=BIT(len(a)+1)\n",
    "\n",
    "        ans=0\n",
    "        #decrete\n",
    "        for x in a:\n",
    "            i=bisect_right(b,x+diff)\n",
    "            ans+=t.query(i)\n",
    "            t.add(bisect_left(b,x)+1,1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "\n",
    "        b = sorted(set(a))\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        t = BIT(len(b) + 1)\n",
    "\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "    \n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree) :\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # n1[i] - n2[i] <= n1[j] - n2[j] + diff\n",
    "        # n[i] <= n[j] + diff\n",
    "        sl = SortedList()\n",
    "        ans = 0\n",
    "        nums = [a - b for a, b in zip(nums1, nums2)]\n",
    "        for num in nums[::-1]:\n",
    "            ans += len(sl) - (sl.bisect_left(num))\n",
    "            sl.add(num+diff)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        ans = 0\n",
    "        sl = SortedList()\n",
    "        for x in (a - b for a, b in zip(nums1, nums2)):\n",
    "            ans += sl.bisect_right(x + diff)\n",
    "            sl.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        li = SortedList()\n",
    "        res = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            if li:\n",
    "                index = li.bisect_right(x - y + diff)\n",
    "                res += index\n",
    "            li.add(x - y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        ans, sl = 0, SortedList()\n",
    "        for a, b in zip(nums1, nums2):\n",
    "            ans += sl.bisect_right(a - b + diff)\n",
    "            sl.add(a - b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList as SL\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        arr = SL()\n",
    "        ans = 0\n",
    "        for a, b in zip(nums1, nums2):\n",
    "            x = a - b\n",
    "            ans += arr.bisect_right(x + diff)\n",
    "            arr.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left, bisect_right\n",
    "# nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "\n",
    "class Solution:\n",
    "  def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "    n = len(nums1)\n",
    "    for i in range(n):\n",
    "      nums1[i] -= nums2[i]\n",
    "    b = sorted(set(nums1))\n",
    "    bit = BIT(len(b))\n",
    "    ans = 0\n",
    "    for x in nums1:\n",
    "      ans += bit.query(bisect_right(b, x + diff))\n",
    "      bit.update(bisect_left(b, x) + 1)\n",
    "    return ans\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # 两个数组相同下标对应数对的插值>= diff\n",
    "        # 转换为逆序对问题： 归并排序(线段树分治) & 树状数组\n",
    "\n",
    "        for i, x in enumerate(nums2):\n",
    "            nums1[i] -= x           # 合并两个数组\n",
    "        a = sorted(set(nums1)) # 离散化， 排序后便于二分\n",
    "\n",
    "        ans = 0 \n",
    "        t = BIT(len(a) + 1)\n",
    "        for x in nums1:   # 遍历nums1\n",
    "            ans += t.query(bisect_right(a, x + diff)) # 找到符合a[i] <= a[j] + diff的数对个数\n",
    "            t.add(bisect_left(a, x) + 1)\n",
    "        return ans \n",
    "    \n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n \n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1 \n",
    "            x += x & -x \n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1 \n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # n1[i] - n2[i] <= n1[j] - n2[j] + diff\n",
    "        # n[i] <= n[j] + diff\n",
    "        sl = SortedList()\n",
    "        ans = 0\n",
    "        nums = [a - b for a, b in zip(nums1, nums2)]\n",
    "        for num in nums:\n",
    "            ans += sl.bisect_right(num+diff)\n",
    "            sl.add(num)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a))  # 配合下面的二分，离散化\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "    def add(self,x):\n",
    "        while x<len(self.tree):\n",
    "            self.tree[x]+=1\n",
    "            x += x&-x\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left, bisect_right\n",
    "# nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "\n",
    "class Solution:\n",
    "  def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "    n = len(nums1)\n",
    "    for i in range(n):\n",
    "      nums1[i] -= nums2[i]\n",
    "    b = sorted(set(nums1))\n",
    "    bit = BIT(len(b))\n",
    "    ans = 0\n",
    "    for x in nums1:\n",
    "      ans += bit.query(bisect_right(b, x + diff))\n",
    "      bit.update(bisect_right(b, x))\n",
    "    return ans\n",
    "\n",
    "class BIT:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  def update(self, i):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += 1\n",
    "      i += i & -i\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # 两个数组，对应下标的数对差值满足条件： \n",
    "        \n",
    "        # 转换成逆序对： 归并排序 & 树状数组\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a)) # 配合二分，离散化\n",
    "        \n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # 两个数组相同下标对应数对的插值>= diff\n",
    "        # 转换为逆序对问题： 归并排序(线段树分治) & 树状数组\n",
    "\n",
    "        for i, x in enumerate(nums2):\n",
    "            nums1[i] -= x \n",
    "        a = sorted(set(nums1)) # 离散化， 排序后便于二分\n",
    "\n",
    "        ans = 0 \n",
    "        t = BIT(len(a) + 1)\n",
    "        for x in nums1:\n",
    "            ans += t.query(bisect_right(a, x + diff))\n",
    "            t.add(bisect_left(a, x) + 1)\n",
    "        return ans \n",
    "    \n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n \n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1 \n",
    "            x += x & -x \n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1 \n",
    "        return res \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a))  # 配合下面的二分，离散化\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a))  # 配合下面的二分，离散化\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a))  # 配合下面的二分，离散化\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        a=[x-y for x,y in zip(nums1,nums2)]\n",
    "        li=sorted(set(a))\n",
    "        d={v:i for i,v in enumerate(li)}\n",
    "        n=len(li)\n",
    "\n",
    "        ta=[0]*(n+1)\n",
    "        def add(x):\n",
    "            while x<=n:\n",
    "                ta[x]+=1\n",
    "                x+=x&(-x)\n",
    "            return \n",
    "        def query(x):\n",
    "            # print(x)\n",
    "            ans=0\n",
    "            while x:\n",
    "                ans+=ta[x]\n",
    "                x&=x-1\n",
    "            return ans\n",
    "\n",
    "        ans=0\n",
    "        for x in a:\n",
    "            ans+=query(bisect_right(li,x+diff))\n",
    "            add(d[x]+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        nums = [num1-num2 for num1, num2 in zip(nums1, nums2)]\n",
    "        n = len(nums)\n",
    "        maxnum, minnum = float('-inf'), float('inf')\n",
    "        for num in nums:\n",
    "            maxnum = max(maxnum, num)\n",
    "            minnum = min(minnum, num)\n",
    "        dp = [0]*(maxnum-minnum+1+1)\n",
    "        def lowbit(i):\n",
    "            return i & -i \n",
    "        def add(x):\n",
    "            while(x <= maxnum-minnum+1):\n",
    "                dp[x] += 1\n",
    "                x += lowbit(x)\n",
    "            return\n",
    "        def subsum(x):\n",
    "            rsum = 0\n",
    "            while(x > 0):\n",
    "                rsum += dp[x]\n",
    "                x -= lowbit(x)\n",
    "            return rsum \n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            result += subsum(min(num-minnum+1+diff, maxnum-minnum+1))\n",
    "            add(num-minnum+1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            nums1[i] -= x\n",
    "        b = sorted(set(nums1))  # 配合下面的二分，离散化\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in nums1:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        nums = [num1-num2 for num1, num2 in zip(nums1, nums2)]\n",
    "        n = len(nums)\n",
    "        maxnum, minnum = float('-inf'), float('inf')\n",
    "        for num in nums:\n",
    "            maxnum = max(maxnum, num)\n",
    "            minnum = min(minnum, num)\n",
    "        dp = [0]*(maxnum-minnum+1+1)\n",
    "        def lowbit(i):\n",
    "            return i & -i \n",
    "        def add(x):\n",
    "            while(x <= maxnum-minnum+1):\n",
    "                dp[x] += 1\n",
    "                x += lowbit(x)\n",
    "            return\n",
    "        def subsum(x):\n",
    "            rsum = 0\n",
    "            while(x > 0):\n",
    "                rsum += dp[x]\n",
    "                x -= lowbit(x)\n",
    "            return rsum \n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            result += subsum(min(num-minnum+1+diff, maxnum-minnum+1))\n",
    "            add(num-minnum+1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i,x in enumerate(nums2):\n",
    "            nums1[i] -= x\n",
    "        mp = {}\n",
    "        for index, x in enumerate(sorted(nums1 + [y+diff for y in nums1]), start=1):\n",
    "            mp[x] = index\n",
    "        n=index\n",
    "        bit = Bit(n)\n",
    "\n",
    "        ans = 0\n",
    "        for i in nums1:\n",
    "            ans += bit.prefixSum(mp[i+diff])\n",
    "            bit.add(mp[i], 1)\n",
    "        return ans  \n",
    "\n",
    "class Bit:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0] * (n+1)\n",
    "        self.n = n\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & -x\n",
    "    \n",
    "    def add(self, i, v):\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += v\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def prefixSum(self, i):\n",
    "        s = 0\n",
    "        while i > 0:\n",
    "            s += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "      def merge_sort(arr):\n",
    "          if len(arr)==1:\n",
    "              return 0\n",
    "          m=len(arr)//2\n",
    "          cnt=0\n",
    "          a=arr[:m]\n",
    "          b=arr[m:]\n",
    "          cnt+=merge_sort(a)+merge_sort(b)\n",
    "          i=0\n",
    "          n=len(a)\n",
    "          for x in b:\n",
    "              while i<n and a[i]<=x+diff:\n",
    "                  i+=1\n",
    "              cnt+=i    \n",
    "          cur=i=j=0\n",
    "          m=len(b)\n",
    "          while True:\n",
    "             if i==n:\n",
    "                 arr[cur:]=b[j:]\n",
    "                 break\n",
    "             if j==m:\n",
    "                 arr[cur:]=a[i:]\n",
    "                 break    \n",
    "             if a[i]<b[j]:\n",
    "                 arr[cur]=a[i]\n",
    "                 i+=1\n",
    "                 cur+=1\n",
    "             else:\n",
    "                 arr[cur]=b[j]\n",
    "                 cur+=1\n",
    "                 j+=1\n",
    "          return cnt   \n",
    "      a=[x-y for x,y in zip(nums1,nums2)]\n",
    "      return merge_sort(a)  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        #o(n**2)过不了 不能暴力\n",
    "        record = [0]*len(nums1)\n",
    "        for i in range(len(nums1)):\n",
    "            record[i] = nums1[i]- nums2[i]\n",
    "        def merge_sort(arr):\n",
    "            if len(arr) <= 1:\n",
    "                return 0\n",
    "            mid = len(arr)//2\n",
    "            # count = 0\n",
    "            a = arr[:mid]\n",
    "            b = arr[mid:]\n",
    "            count = merge_sort(a) + merge_sort(b)\n",
    "            index = 0\n",
    "            for i in b:\n",
    "                while index < len(a) and i - a[index]+diff>=0:\n",
    "                    index+=1\n",
    "                count+=index\n",
    "            # for data in b:\n",
    "                # while index<len(a) and data- \n",
    "            i = j = cur = 0\n",
    "            while True:\n",
    "                if i == len(a):\n",
    "                    arr[cur:] = b[j:]\n",
    "                    break\n",
    "                elif j == len(b):\n",
    "                    arr[cur:] = a[i:]\n",
    "                    break\n",
    "                else:\n",
    "                    if a[i]>b[j]:\n",
    "                        arr[cur] = b[j]\n",
    "                        cur+=1\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        arr[cur] = a[i]\n",
    "                        cur+=1\n",
    "                        i+=1\n",
    "            return count\n",
    "        return merge_sort(record)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # 转换成逆序对： 归并排序，树状数组\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a)) # 配合二分，离散化\n",
    "        \n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        res = 0\n",
    "        sorted_arr = []\n",
    "        for i in range(len(nums1)):\n",
    "            val = nums1[i] - nums2[i]\n",
    "            idx = bisect_right(sorted_arr, val)\n",
    "            res += idx\n",
    "            insort(sorted_arr, val - diff)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def init(self,n):\n",
    "        self.n = n\n",
    "        self.tree = [0]*(n+1)\n",
    "    def update(self,k,x):\n",
    "        while k <= self.n:\n",
    "            self.tree[k]+=x\n",
    "            k += k & -k\n",
    "    def get_sum(self,k):\n",
    "        s = 0\n",
    "        while k > 0:\n",
    "            s+=self.tree[k]\n",
    "            k-= k & -k\n",
    "        return s\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        nums = [x - y for x , y in zip(nums1,nums2)]\n",
    "        nums2 = nums +  [x - y - diff for x , y in zip(nums1,nums2)]\n",
    "        q = {}\n",
    "        index = 0\n",
    "        for num in sorted(set(nums2)):\n",
    "            index+=1\n",
    "            q[num]=index\n",
    "        self.init(len(set(nums2)))\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            count+=self.get_sum(q[num])\n",
    "            self.update(q[num-diff],1)\n",
    "        return count\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Bit:\n",
    "    def __init__(self,n):\n",
    "        self.arr = [0]*n\n",
    "    def add(self,index,v=1):\n",
    "        while index<len(self.arr):\n",
    "            self.arr[index]+=v\n",
    "            index += index&(-index)\n",
    "    def query(self,index):\n",
    "        ans = 0\n",
    "        while index>0:\n",
    "            ans+=self.arr[index]\n",
    "            index &= index-1\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        arr = [x-y for x,y in zip(nums1,nums2)]\n",
    "        arr1 = sorted(arr)\n",
    "        res = 0\n",
    "        n = len(nums1)\n",
    "        tree = Bit(n+1)\n",
    "        ans = 0\n",
    "        for v in arr:\n",
    "            i = bisect_right(arr1,v+diff)\n",
    "            ans+=tree.query(i)\n",
    "            tree.add(bisect_left(arr1,v)+1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        #o(n**2)过不了 不能暴力\n",
    "        # record = [0]*len(nums1)\n",
    "        # for i in range(len(nums1)):\n",
    "        #     record[i] = nums1[i]- nums2[i]\n",
    "        # def merge_sort(arr):\n",
    "        #     if len(arr) <= 1:\n",
    "        #         return 0\n",
    "        #     mid = len(arr)//2\n",
    "        #     # count = 0\n",
    "        #     a = arr[:mid]\n",
    "        #     b = arr[mid:]\n",
    "        #     count = merge_sort(a) + merge_sort(b)\n",
    "        #     index = 0\n",
    "        #     for i in b:\n",
    "        #         while index < len(a) and i - a[index]+diff>=0:\n",
    "        #             index+=1\n",
    "        #         count+=index\n",
    "        #     # for data in b:\n",
    "        #         # while index<len(a) and data- \n",
    "        #     i = j = cur = 0\n",
    "        #     while True:\n",
    "        #         if i == len(a):\n",
    "        #             arr[cur:] = b[j:]\n",
    "        #             break\n",
    "        #         elif j == len(b):\n",
    "        #             arr[cur:] = a[i:]\n",
    "        #             break\n",
    "        #         else:\n",
    "        #             if a[i]>b[j]:\n",
    "        #                 arr[cur] = b[j]\n",
    "        #                 cur+=1\n",
    "        #                 j+=1\n",
    "        #             else:\n",
    "        #                 arr[cur] = a[i]\n",
    "        #                 cur+=1\n",
    "        #                 i+=1\n",
    "        #     return count\n",
    "        # return merge_sort(record)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "\n",
    "        b = sorted(set(a))\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        t = BIT(len(b) + 1)\n",
    "\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "    \n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree) :\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        n = len(nums1)\n",
    "        MX = 6*(10**4)\n",
    "        tree = [0]*(MX+1)\n",
    "\n",
    "        def lowbit(x):\n",
    "            return x & -x\n",
    "        def add(pos,v):\n",
    "            while pos <=MX:\n",
    "                tree[pos]+=v\n",
    "                pos+=lowbit(pos)\n",
    "        def query(pos):\n",
    "            ret = 0\n",
    "            while pos:\n",
    "                print(pos)\n",
    "                ret += tree[pos]\n",
    "                pos -= lowbit(pos)\n",
    "            return ret\n",
    "        ans = 0\n",
    "        arr = []\n",
    "        for a,b in zip(nums1,nums2):\n",
    "            arr.append(a-b)\n",
    "        mn = min(arr)\n",
    "        # print(arr)\n",
    "        if mn <=0:\n",
    "            for i in range(n):\n",
    "                arr[i]+=(-mn+1+10**4)\n",
    "        # print(arr)\n",
    "        # print(max(arr))\n",
    "        for x in arr:\n",
    "            \n",
    "            ans+=query(x+diff)\n",
    "            add(x,1)\n",
    "            # print(x-1+diff,ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NodeIndexedTree:\n",
    "    def __init__(self, length):\n",
    "        self.n = length\n",
    "        self.tree = [0]*(length+1)\n",
    "    def lowbit(self,  x):\n",
    "        return x & (-x)\n",
    "    def update(self, x, val):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += val\n",
    "            x += self.lowbit(x)\n",
    "    def query(self,  x):\n",
    "        ans = 0\n",
    "        while x > 0:\n",
    "            ans += self.tree[x]\n",
    "            x -= self.lowbit(x)\n",
    "        return  ans\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        ##树状数组 当题目中给定的条件有困难，需要转化条件\n",
    "        n = len(nums1)\n",
    "        arr = [ nums1[i] - nums2[i] for i in range(n)]\n",
    "        a = arr[:]\n",
    "        for num in arr:\n",
    "            a.append(num +diff)\n",
    "        a = sorted(set(a))\n",
    "        value2Id={v:i+1 for i, v in enumerate(a)}\n",
    "        tree = NodeIndexedTree(len(a))\n",
    "        ans = 0\n",
    "        for i in range(len(arr)):\n",
    "            ans+=tree.query(value2Id[arr[i] + diff])\n",
    "            tree.update(value2Id[arr[i]], 1)\n",
    "        return ans        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a))  # 配合下面的二分，离散化\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        n = len(nums1)\n",
    "        st = SortedList()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cur = nums1[i] - nums2[i] + diff\n",
    "            idx = st.bisect_right(cur)\n",
    "            st.add(nums1[i] - nums2[i])\n",
    "            ans += idx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        s = SortedList()\n",
    "        n = len(nums1)\n",
    "        s.add(nums1[0] - nums2[0])\n",
    "        ret = 0\n",
    "        for i in range(1, n):\n",
    "            k = nums1[i] - nums2[i] + diff\n",
    "            ret += s.bisect_right(k)\n",
    "            s.add(nums1[i] - nums2[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a))  # 配合下面的二分，离散化\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # 这个做法说不准O(nlogn)能够做完\n",
    "        result = 0\n",
    "        n = len(nums1)\n",
    "        difference = [0] * n\n",
    "        for i in range(n):\n",
    "            difference[i] = nums1[i] - nums2[i]\n",
    "        sort = SortedList()\n",
    "        for x in difference:\n",
    "            result += sort.bisect_right(x + diff)\n",
    "            sort.add(x)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "import bisect\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        my_mat=SortedList([])\n",
    "        sum1=0\n",
    "        for i in range(len(nums1)):\n",
    "            tempv=nums1[i]-nums2[i]\n",
    "            index1=bisect.bisect_right(my_mat,tempv+diff)\n",
    "            sum1+=index1-0\n",
    "            my_mat.add(tempv)\n",
    "\n",
    "        return sum1\n",
    "\n",
    "        # my_mat=[]\n",
    "        # for i in range(len(nums1)):\n",
    "        #     my_mat.append(nums1[i]-nums2[i])\n",
    "        # temp=[0]*len(nums1)\n",
    "        # def twomerge(l,r):\n",
    "        #     if l>=r:\n",
    "        #         return 0\n",
    "        #     mid=(l+r)//2\n",
    "        #     sum1=twomerge(l,mid)+twomerge(mid+1,r)\n",
    "        #     left_index=l\n",
    "        #     right_index=mid+1\n",
    "        #     while left_index<=mid:\n",
    "        #         while right_index<=r and my_mat[left_index]>my_mat[right_index]+diff:\n",
    "        #             right_index+=1\n",
    "        #         sum1+=r-right_index+1\n",
    "        #         left_index+=1\n",
    "        #     left_index2=l\n",
    "        #     right_index2=mid+1\n",
    "        #     pos_index=l\n",
    "        #     while left_index2<=mid and right_index2<=r:\n",
    "        #         if my_mat[left_index2]<=my_mat[right_index2]:\n",
    "        #             temp[pos_index]=my_mat[left_index2]\n",
    "        #             left_index2+=1\n",
    "        #             pos_index+=1\n",
    "        #         else:\n",
    "        #             temp[pos_index]=my_mat[right_index2]\n",
    "        #             right_index2+=1\n",
    "        #             pos_index+=1\n",
    "        #     while left_index2<=mid:\n",
    "        #         temp[pos_index]=my_mat[left_index2]\n",
    "        #         left_index2+=1\n",
    "        #         pos_index+=1\n",
    "        #     while right_index2<=r:\n",
    "        #         temp[pos_index]=my_mat[right_index2]\n",
    "        #         right_index2+=1\n",
    "        #         pos_index+=1\n",
    "        #     for i in range(l,r+1):\n",
    "        #         my_mat[i]=temp[i]\n",
    "        #     return sum1\n",
    "\n",
    "        # return twomerge(0,len(nums1)-1)\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "\n",
    "\n",
    "        def mergesort(arr: List[int]) -> int :\n",
    "            if len(arr) <= 1:\n",
    "                return 0\n",
    "\n",
    "            mid = len(arr) // 2\n",
    "            a = arr[: mid]\n",
    "            b = arr[mid: ]\n",
    "            cnt = mergesort(a) + mergesort(b)\n",
    "\n",
    "            i, n = 0, len(a)\n",
    "\n",
    "            for x in b:\n",
    "                while i < n and a[i] <= x + diff:\n",
    "                    i += 1\n",
    "                cnt += i\n",
    "            \n",
    "            cur = i = j = 0\n",
    "\n",
    "            m = len(b)\n",
    "\n",
    "            while True:\n",
    "                if i == n:\n",
    "                    arr[cur: ] = b[j: ]\n",
    "                    break\n",
    "                if j == m:\n",
    "                    arr[cur: ] = a[i: ]\n",
    "                    break\n",
    "\n",
    "                if a[i] < b[j]:\n",
    "                    arr[cur] = a[i]\n",
    "                    cur += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    arr[cur] = b[j]\n",
    "                    cur += 1\n",
    "                    j += 1\n",
    "            return cnt\n",
    "\n",
    "        a = [x - y for x, y in zip(nums1, nums2)]\n",
    "        return mergesort(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        sl = SortedList()\n",
    "        ans = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            tar = x - y + diff \n",
    "            ans += sl.bisect_right(tar)\n",
    "            sl.add(x - y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        import sortedcontainers\n",
    "        l = [i-j for i, j in zip(nums1, nums2)]\n",
    "        sl = sortedcontainers.SortedList([i+diff for i in l])\n",
    "        res = 0\n",
    "        for i in l:\n",
    "            sl.remove(i+diff)\n",
    "            res += len(sl)-sl.bisect_left(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        diffs = SortedList()\n",
    "        res = 0\n",
    "        for i, (n1, n2) in enumerate(zip(nums1, nums2)):\n",
    "            off = diffs.bisect_right(n1 - n2 + diff)\n",
    "            res += off\n",
    "            diffs.add(n1 - n2)\n",
    "        return res\n",
    "        # nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        ##设nums3[i]=nums1[i]-nums2[i]\n",
    "        ##求nums3[i]<=nums3[j]+diff\n",
    "        ans=0\n",
    "        n=len(nums1)\n",
    "        nums3=SortedList()\n",
    "        for i in range(n):\n",
    "            cur=nums1[i]-nums2[i]\n",
    "            ans+=bisect_right(nums3,cur+diff)\n",
    "            nums3.add(cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        ans, s = 0, SortedList()\n",
    "        for x in (a - b for a, b in zip(nums1, nums2)):\n",
    "            ans += s.bisect_right(x + diff)\n",
    "            s.add(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "# sys.set_int_max_str_digits(0)  # 大数的范围坑\n",
    "\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        n = len(nums1)\n",
    "        ans = 0\n",
    "        lst = SortedList()\n",
    "        for i in range(n):\n",
    "            ans += lst.bisect_right(nums1[i]-nums2[i]+diff)\n",
    "            lst.add(nums1[i]-nums2[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        n = len(nums1)\n",
    "        L = [x - y for x, y in zip(nums1, nums2)]\n",
    "        sl = SortedList()\n",
    "        ans = 0\n",
    "        for x, y in zip(nums1, nums2):\n",
    "            tar = x - y + diff \n",
    "            ans += sl.bisect_right(tar)\n",
    "            sl.add(x - y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        arr = set()\n",
    "        n = len(nums1)\n",
    "        for i in range(n):\n",
    "            arr.add(nums1[i] - nums2[i])\n",
    "            arr.add(nums1[i] - nums2[i] + diff)\n",
    "        ar = sorted(arr)\n",
    "        size = len(ar)\n",
    "        idxs = {}\n",
    "        print (size)\n",
    "        for i in range(size):\n",
    "            # print (f'idxs[ar[{i}]] = {i + 1}')\n",
    "            idxs[ar[i]] = i + 1\n",
    "        tree = [0] * (size + 1)\n",
    "\n",
    "        def query(i):\n",
    "            count = 0\n",
    "            while i > 0:\n",
    "                count += tree[i]\n",
    "                i -= i & -i\n",
    "            return count\n",
    "        def update(i):\n",
    "            while i < size + 1:\n",
    "                tree[i] += 1\n",
    "                i += i & -i\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            val = nums1[i] - nums2[i]\n",
    "            ret += query(idxs[val + diff])\n",
    "            update(idxs[val])\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        \"\"\"\n",
    "        nums1[i] - nums1[j] <= num2[i] - nums2[j] + diff\n",
    "        =>  nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "        =>  nums3[i] <= nums3[j] + diff\n",
    "        树状数组/线段树\n",
    "        \"\"\"\n",
    "        n = len(nums1)\n",
    "        nums3 = [nums1[i]- nums2[i] for i in range(n)]\n",
    "        b = sorted(set(nums3))\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in nums3:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < self.n:\n",
    "            self.tree[x] += 1\n",
    "            # 用于求出x最右边的bit\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 离散化树状数组\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a))  # 配合下面的二分，离散化\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, a: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            a[i] -= x\n",
    "        b = sorted(set(a))  # 配合下面的二分，离散化\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in a:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        \"\"\"\n",
    "        nums1[i] - nums1[j] <= num2[i] - nums2[j] + diff\n",
    "        =>  nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff\n",
    "        =>  nums3[i] <= nums3[j] + diff\n",
    "        树状数组/线段树\n",
    "        \"\"\"\n",
    "        n = len(nums1)\n",
    "        nums3 = [nums1[i]- nums2[i] for i in range(n)]\n",
    "        b = sorted(set(nums3))\n",
    "        ans = 0\n",
    "        t = BIT(len(b) + 1)\n",
    "        for x in nums3:\n",
    "            ans += t.query(bisect_right(b, x + diff))\n",
    "            t.add(bisect_left(b, x) + 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        for i, x in enumerate(nums2):\n",
    "            nums1[i] -= x\n",
    "        nums=set(nums1)\n",
    "        tmp=[]\n",
    "        for x in nums:\n",
    "            tmp.append(x)\n",
    "            tmp.append(x-diff)\n",
    "            tmp.append(x+diff)\n",
    "        nums=sorted(list(set(tmp)))\n",
    "        d={}\n",
    "        for i,num in enumerate(nums):\n",
    "            d[num]=i+1\n",
    "\n",
    "        ans = 0\n",
    "        t = BIT(len(nums) + 1)\n",
    "        for x in nums1:\n",
    "            ans += t.query(d[x+diff])\n",
    "            t.add(d[x])\n",
    "        return ans\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * n\n",
    "\n",
    "    def add(self, x):\n",
    "        while x < len(self.tree):\n",
    "            self.tree[x] += 1\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]\n",
    "            x &= x - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class treeArray:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "\n",
    "    # c[i] += val\n",
    "    def update(self, i, val): \n",
    "        i += 1\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += val\n",
    "            i += i & -i\n",
    "    \n",
    "    # sum(c[:i])\n",
    "    def getSum(self, i):\n",
    "        ans = 0\n",
    "        while i:\n",
    "            ans += self.tree[i]\n",
    "            i -= i & -i\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # n1[i] - n2[i] <= n1[j] - n2[j] + diff\n",
    "        # n[i] <= n[j] + diff\n",
    "        nums = [a - b for a, b in zip(nums1, nums2)]\n",
    "        # 离散化\n",
    "        candidates = set()\n",
    "        for num in nums:\n",
    "            candidates.update([num, num+diff])\n",
    "        candidates = list(candidates)\n",
    "        candidates.sort()\n",
    "        valid_id = dict()\n",
    "        for i, c in enumerate(candidates):\n",
    "            valid_id[c] = i\n",
    "        \n",
    "        ans = 0\n",
    "        treearr = treeArray(len(candidates))\n",
    "        for num in nums:\n",
    "            idx = valid_id[num+diff]\n",
    "            ans += treearr.getSum(idx+1)\n",
    "            treearr.update(valid_id[num], 1)\n",
    "        \n",
    "        return ans\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, nn: int):\n",
    "        self.n = nn + 2\n",
    "        self.tree = [0] * (self.n)\n",
    "    def update(self, i: int, dis: int):\n",
    "        while i < self.n:\n",
    "            self.tree[i] += dis \n",
    "            i += i & -i\n",
    "    def ssum(self, i: int):\n",
    "        res = 0\n",
    "        while i:\n",
    "            res += self.tree[i] \n",
    "            i -= i & -i\n",
    "        return res\n",
    "class Solution:\n",
    "    def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:\n",
    "        # nums1[i] - nums2[i] <= nums1[j] - nums2[j] + diff \n",
    "        # 若 f[i] = nums1[i] - nums2[i] \n",
    "        # 有 f[i] <= f[j] + diff i < j\n",
    "        \"\"\"\n",
    "        如果 diff = 0 \n",
    "        问题等价于求 逆序对个数 最终结果为 n * (n - 1) // 2 - 逆序对个数\n",
    "        f[i] - diff > f[j]\n",
    "        \"\"\"\n",
    "        n = len(nums1)\n",
    "        nums = [nums1[i] - nums2[i] + 2 * 10 ** 4 + 1 for i in range(n)]\n",
    "        mx = max(nums)\n",
    "        root = BIT(mx + 10 ** 4 + 1)\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans[i] = root.ssum(max(nums[i] - 1 - diff, 0))\n",
    "            root.update(nums[i], 1)\n",
    "        return n * (n - 1) // 2 - sum(ans)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
